在 JavaScript 中，Map 是用于存储键值对的集合类型，其底层数据结构的设计直接影响了键的多样性（支持任意类型）、顺序性（插入顺序）和操作性能（增删查效率）。不同 JavaScript 引擎（如 V8、SpiderMonkey、JavaScriptCore）对 Map 的实现细节略有差异，但核心思想一致：结合哈希表（Hash Table）和有序数据结构（如双向链表），兼顾快速查找和顺序维护。
一、核心设计目标
Map 的底层实现需要满足以下关键需求：
- 支持任意类型的键（字符串、数字、对象、函数等），且键的比较基于
SameValueZero算法（类似===，但NaN视为相等）。 - 保持插入顺序（ES6 规范要求，遍历顺序与插入顺序一致）。
- 高效的增删查操作（平均时间复杂度接近 O(1)）。
二、V8 引擎中 Map 的底层实现（最具代表性）
V8 引擎（Chrome、Node.js 等使用）对 Map 的实现是业界主流参考，其核心结构是 “哈希表 + 双向链表” 的混合设计，具体分为两个关键部分：
1. 哈希表（Hash Table）：快速查找
哈希表是 Map 实现快速访问的基础，用于根据键（key）快速定位对应的值（value）。
哈希函数：
对于任意类型的键，V8 会通过一个哈希函数生成一个唯一的哈希值（hash code）。例如：- 原始类型（字符串、数字）：直接基于值计算哈希（如字符串通过字符编码哈希，数字直接用其值）。
- 对象类型（数组、对象、函数等）：使用对象的内存地址或内部唯一标识计算哈希（确保不同对象即使内容相同，哈希值也不同）。
- 特殊值（
NaN、-0）：NaN与自身视为相等，-0与0视为不同键，哈希函数会特殊处理以符合SameValueZero规则。
哈希冲突处理：
不同键可能生成相同的哈希值（哈希冲突），V8 采用 “链地址法” 解决：哈希表的每个桶（bucket）中存储一个链表，相同哈希值的键值对会被放入同一个桶的链表中，查找时需遍历链表匹配键。动态扩容：
当哈希表的负载因子（键值对数量 / 桶数量）超过阈值（通常为 0.7）时，会触发扩容：创建一个更大的桶数组（通常是原大小的 2 倍），并将所有键值对重新哈希到新桶中，以减少哈希冲突，保证操作效率。
2. 双向链表（Doubly Linked List）：维护顺序
哈希表本身是无序的，为了满足“插入顺序遍历”的需求，V8 在 Map 中额外维护了一个双向链表，记录键值对的插入顺序。
链表节点结构：
每个键值对在哈希表中存储的同时，也作为双向链表的一个节点，包含prev（上一个节点）和next（下一个节点）指针，以及键值对数据（key、value）。顺序维护：
- 新增键值对时，在哈希表中插入的同时，将节点追加到双向链表的尾部。
- 删除键值对时，从哈希表中移除的同时，调整链表的
prev和next指针，保持链表连续性。 - 遍历
Map时（如for...of、entries()），直接按双向链表的顺序依次访问节点，无需依赖哈希表的无序结构。
3. 数据结构示意图
简化后的结构如下：
Map {
// 哈希表：桶数组，每个桶存储哈希冲突的键值对链表
hashTable: [
bucket1: { key: k1, value: v1, next: null, prev: null, listNext: node2, listPrev: null },
bucket2: { key: k3, value: v3, next: node4, ... }, // 哈希冲突的键在同一桶中
...
],
// 双向链表：维护插入顺序
linkedList: {
head: node1 (k1), // 第一个插入的节点
tail: nodeN (kN), // 最后一个插入的节点
}
}三、其他引擎的实现差异
- SpiderMonkey（Firefox）：早期采用类似 V8 的哈希表 + 链表设计，后期优化为更紧凑的“有序哈希表”，通过数组存储键值对并记录插入索引，减少内存开销。
- JavaScriptCore（Safari）：使用“哈希表 + 有序数组”，数组记录插入顺序，哈希表映射键到数组索引，兼顾性能和顺序。
尽管细节不同，但所有引擎的核心思路一致：用哈希表保证查找效率，用额外结构（链表/数组）维护插入顺序。
四、与 Object 底层的关键区别
Object的键只能是字符串/Symbol（数字会转为字符串），底层哈希表可针对字符串做深度优化（如静态属性的快速查找），但不支持复杂键和顺序。Map支持任意类型键，需额外处理不同类型的哈希计算，且必须维护顺序结构，因此在小规模数据下略逊于Object，但在大规模、动态键场景下更稳定。
总结
Map 的底层是 “哈希表 + 双向链表” 的混合结构：
- 哈希表负责通过键的哈希值快速定位键值对，保证增删查的平均 O(1) 复杂度。
- 双向链表负责记录插入顺序，满足遍历顺序的需求。
- 这种设计使其既能支持任意类型的键，又能保持插入顺序，同时兼顾高效操作，是专门为键值对集合场景优化的数据结构。
贡献者
jiechen